Chứng minh

Đánh số các đỉnh của K n {\displaystyle K_{n}} là v 1 , v 2 , v 3 , … , v n {\displaystyle v_{1},v_{2},v_{3},\ldots ,v_{n}} .

Do mỗi đỉnh của K n {\displaystyle K_{n}} có bậc bằng n-1, nên số màu cạnh của nó không nhỏ hơn n-1, do đó χ'( K n {\displaystyle K_{n}} ) bằng n hoặc n-1.

Chứng minh χ'( K n {\displaystyle K_{n}} )=n-1 với n chẵn:

Ta chỉ cần chỉ ra cách tô n-1 màu cho các cạnh của K n {\displaystyle K_{n}} là được.Ký hiệu các màu là M 1 , M 2 , … , M n − 1 {\displaystyle M_{1},M_{2},\ldots ,M_{n-1}} .Ma trận dưới đây biểu thị cách tô màu, trong đó:

• giá trị ở hàng thứ i cột j chính là màu được gán cho cạnh ( v i , v j ) {\displaystyle (v_{i},v_{j})} ;
• X nghĩa là không được gán màu.

v 1 v 2 v 3 v 4 ⋯ v n − 2 v n − 1 v n v 1 X M 1 M 2 M 3 ⋯ M n − 3 M n − 2 M n − 1 v 2 M 1 X M 3 M 4 ⋯ M n − 2 M n − 1 M 2 v 3 M 2 M 3 X M 5 ⋯ M n − 1 M 1 M 4 v 4 M 3 M 4 M 5 X ⋯ M 1 M 2 M 6 ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮ v n M n − 1 M 2 M 4 M 6 ⋯ ⋯ ⋯ X . {\displaystyle {\begin{matrix}&v_{1}&v_{2}&v_{3}&v_{4}&\cdots &v_{n-2}&v_{n-1}&v_{n}\\v_{1}&X&M_{1}&M_{2}&M_{3}&\cdots &M_{n-3}&M_{n-2}&M_{n-1}\\v_{2}&M_{1}&X&M_{3}&M_{4}&\cdots &M_{n-2}&M_{n-1}&M_{2}\\v_{3}&M_{2}&M_{3}&X&M_{5}&\cdots &M_{n-1}&M_{1}&M_{4}\\v_{4}&M_{3}&M_{4}&M_{5}&X&\cdots &M_{1}&M_{2}&M_{6}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\\v_{n}&M_{n-1}&M_{2}&M_{4}&M_{6}&\cdots &\cdots &\cdots &X\end{matrix}}.} Ví dụ với n=6, ta có cách tô màu như sau: v 1 v 2 v 3 v 4 v 5 v 6 v 1 X M 1 M 2 M 3 M 4 M 5 v 2 M 1 X M 3 M 4 M 5 M 2 v 3 M 2 M 3 X M 5 M 1 M 4 v 4 M 3 M 4 M 5 X M 2 M 1 v 5 M 4 M 5 M 1 M 2 X M 3 v 6 M 5 M 2 M 4 M 1 M 3 X {\displaystyle {\begin{matrix}&v_{1}&v_{2}&v_{3}&v_{4}&v_{5}&v_{6}\\v_{1}&X&M_{1}&M_{2}&M_{3}&M_{4}&M_{5}\\v_{2}&M_{1}&X&M_{3}&M_{4}&M_{5}&M_{2}\\v_{3}&M_{2}&M_{3}&X&M_{5}&M_{1}&M_{4}\\v_{4}&M_{3}&M_{4}&M_{5}&X&M_{2}&M_{1}\\v_{5}&M_{4}&M_{5}&M_{1}&M_{2}&X&M_{3}\\v_{6}&M_{5}&M_{2}&M_{4}&M_{1}&M_{3}&X\\\end{matrix}}}

Chứng minh χ'( K n {\displaystyle K_{n}} )=n với n lẻ:

Trái lại, giả sử tồn tại n lẻ sao cho χ'( K n {\displaystyle K_{n}} ) = n-1.Xét màu M bất kì, các cạnh tô màu M ký hiệu là ( v i 1 , v j 1 ) , ( v i 2 , v j 2 ) , … , ( v i k , v j k ) {\displaystyle (v_{i_{1}},v_{j_{1}}),(v_{i_{2}},v_{j_{2}}),\ldots ,(v_{i_{k}},v_{j_{k}})} , trong đó v i 1 , v j 1 , v i 2 , v j 2 , … , v i k , v j k {\displaystyle v_{i_{1}},v_{j_{1}},v_{i_{2}},v_{j_{2}},\ldots ,v_{i_{k}},v_{j_{k}}} là các đầu mút đôi một phân biệt. Như vậy có 2k đỉnh có cạnh liên thuộc tô bởi màu M, mà n lẻ nên tồn tại ít nhất một đỉnh v i {\displaystyle v_{i}} nào đó không có cạnh liên thuộc tô bởi màu M. Như vậy các cạnh liên thuộc với đỉnh v i {\displaystyle v_{i}} chỉ được tô bởi không quá n-2 màu, mà d e g ( a ) = n − 1 {\displaystyle deg(a)=n-1} (vô lý).